﻿using System;
using System.Collections.Generic;

namespace SLG_Demo_0
{
	public class PathFinding
	{
		// 便于调试查看的搜寻路径列表
		private List<CellData> m_lSearch = null;

		private PathFinding() { }

		private static PathFinding instance;
		public static PathFinding Instance
		{
			get
			{
				if (instance == null)
				{
					instance = new PathFinding();
					instance.Init();
				}
				return instance;
			}
		}

		private void Init()
		{
			if (m_lSearch != null)
			{
				m_lSearch.Clear();
				m_lSearch = null;
			}
		}

		private class PathData
		{
			public PathData m_pPrePath	= null;
			public CellData m_pCellData	= null;

			public bool m_bOpen	= false;

			public int F	= 0;   // F == G + H
			public int G	= 0;   // 从起点移动到指定方格的移动代价
			public int H	= 0;   // Manhattan 距离：从指定的方格移动到终点的估算成本，不考虑阻挡等因素

			public PathData()
			{
				Reset();
			}

			void Reset()
			{
				m_pPrePath	= null;
				m_pCellData	= null;

				F	= 0;
				G	= 0;
				H	= 0;

				m_bOpen	= false;
			}

			public bool FindCompare(PathData other)
			{
				CellData otherCellData = other.m_pCellData;
				if (m_pCellData == null && otherCellData == null)
				{
					return true;
				}
				else if (m_pCellData != null && otherCellData == null)
				{
					return false;
				}
				else if (m_pCellData == null && otherCellData != null)
				{
					return false;
				}
				else
				{
					if ((m_pCellData.Row == otherCellData.Row &&
						m_pCellData.Col == otherCellData.Col))
					{
						return true;
					}
					else
					{
						return false;
					}
				}
			}
		}//end class: PathData



		private PathData NewEmptyPath(CellData pCellData, PathData pPrePath, int nG, int nH)
		{
			PathData newData = null;

			// TODO: 暂时用 new，后改为用通用对象池实现
			newData = new PathData();

			newData.m_pCellData	= pCellData;
			newData.m_pPrePath	= pPrePath;

			newData.G	= nG;
			newData.H	= nH;
			newData.F	= nG + nH;

			newData.m_bOpen	= true;

			return newData;
		}

		//public bool Search(MapData pMapData, CellData pSrcCell, CellData pDstCell, List<CellData> pPath)
		public bool Search(MapData pMapData, CellData pSrcCell, CellData pDstCell, List<CellData> pPath)
		{
			if (pMapData == null || pSrcCell == null || pDstCell == null || pPath == null)
			{
				return false;
			}

			if (pPath != null && pPath.Count != 0)
			{
				pPath.Clear();
			}

			// openlist 列表
			List<PathData> openlist = new List<PathData>();
			// closelist 列表
			List<CellData> closelist = new List<CellData>();

			// 寻路成功标记位
			bool bSuccess = false;

			// 将起点加入 openlist 列表
			int distance = pSrcCell.Distance(pDstCell);
			PathData srcPath = NewEmptyPath(pSrcCell, null, 0, distance);
			openlist.Add(srcPath);

			for (int iSearch = 0; iSearch < pMapData.CellNum; ++iSearch)
			{
				// 寻路成功
				if (bSuccess)
				{
					break;
				}

				// 遍历 open list ，查找 F 值最小的节点，把它作为当前要处理的节点
				int minF = 99999;// 一个很大的值，TODO: 改为C#定义的极大值
				int idx_do = 0;
				for (int iopen = openlist.Count - 1; iopen >= 0 ; --iopen)
				{
					// 已经在 closelist 内的不考虑
					CellData findData = closelist.Find(openlist[iopen].m_pCellData.FindCompare);
					if (findData != null)
					{
						continue;
					}

					if (openlist[iopen].F < minF)
					{
						idx_do = iopen;
						minF = openlist[iopen].F;
					}
				}

				// 找到当前要处理的节点，标志位设为关闭
				PathData curPath = openlist[idx_do];
				curPath.m_bOpen = false;
				closelist.Add(curPath.m_pCellData);
				pPath.Add(curPath.m_pCellData);

				//m_lSearch.Add(curPath.m_pCellData);

				// 依次遍历该节点周围相邻的6个格子
				int roadbit = curPath.m_pCellData.m_PassBit;
				
				for (ECellDir eDir = ECellDir._12; eDir < ECellDir.Max; ++eDir)
				{
					CellData adjacentCellData = curPath.m_pCellData.GetAdjacentCellData(eDir);
					
					// TODO: 判断 adjacentCellData 是否在 closelist 里面
					// Note: CellData 判断不了标志位 open
					// 但是如果真的增加一个 closelist，无疑将大大增加搜索时间（需要每次都检查在不在 closelist 里）

					if (adjacentCellData == null)
					{
						continue;
					}

					if (adjacentCellData.DataType == ECellDataType.Obstacle)
					{
						continue;
					}

					// 在 closelist 列表的不做操作
					if (closelist.Find(adjacentCellData.FindCompare) != null)
					{
						continue;
					}

					// 生成每个相邻格子的 PathData（G、H、F），
					// 并将当前格子 curPath 置为相邻格子的父格子（prePath）
					// 每个相邻格子的G值（从相邻格子到自己的距离）是等距，设为1
					// 每个相邻格子的H值，为这个相邻格子到目的格子的 Distance()
					int adj_G = adjacentCellData.GValue();
					int adj_H = adjacentCellData.Distance(pDstCell);
					PathData adjPath = NewEmptyPath(adjacentCellData, curPath, adj_G, adj_H);

					// 不在 openlist 则置入 openlist 里，等候下次处理
					PathData findPathData = openlist.Find(adjPath.FindCompare);
					if (findPathData == null)
					{
						// 如果把终点加入到 openlist 里，则寻路完成
						if (adjacentCellData == pDstCell)
						{
							pPath.Add(adjacentCellData);
							bSuccess = true;
							break;
						}
						openlist.Add(adjPath);
						continue;
					}

					// 寻路成功，不用再做剩余操作了
					if (bSuccess)
					{
						break;
					}

					// 如果它已经在 open list 中，
					// 检查这条路径 ( 即经由当前方格到达它那里 ) 是否更好，用 G 值作参考。
					// 更小的 G 值表示这是更好的路径。
					// 如果是这样，把它的父亲设置为当前方格，并重新计算它的 G 和 F 值。
					// 如果你的 open list 是按 F 值排序的话，改变后你可能需要重新排序。
					int cur_2_adj_G = curPath.m_pCellData.Distance(adjPath.m_pCellData);
					if (cur_2_adj_G < adjPath.G)
					{
						adjPath.m_pPrePath = curPath;
						adjPath.G = cur_2_adj_G;
						adjPath.H = adjPath.m_pCellData.Distance(pDstCell);
						adjPath.F = adjPath.G + adjPath.H;
					}
				}//end for: eDir
			}// end for: iSearch


			return bSuccess;
		}
	}
}
